package zoran.wang.dp;

import java.util.Arrays;

/**
 * 带备忘录的递归算法
 *
 * @author wangzhuo
 * @time 2025-04-11-16:41
 */
public class Recursive {

    // 记录递归次数，便于查看备忘录的作用
    private int count = 0;

    /**
     * 斐波那契数列
     *
     * @param n,n>=0
     * @return 斐波那契数列中第 n 个数的值
     */
    public int fibonacciSequence(int n) throws Exception {

        // 参数验证
        if (n < 0) throw new Exception("n为非负整数！");

        // 避免 memo[1] 的数组下标越界异常
        if (n == 0) return 0;

        int[] memo = new int[n + 1];

        // base case
        memo[0] = 0;
        memo[1] = 1;

        return fib(memo, n);
    }

    // 定义：斐波那契数列中第 n 个数的值
    private int fib(int[] memo, int n) {

        // base case
        if (n == 0) return 0;
        if (n == 1) return 1;

        return fib(memo, n - 1) + fib(memo, n - 2);
    }

    /**
     * 凑硬币问题，递归不带备忘录
     *
     * @param coins  硬币面额
     * @param amount 需要凑的总金额
     * @return 凑 amount 需要的最小硬币数量，凑不出来时返回 -1
     */
    public int coinChange(int[] coins, int amount) {

        int res = dp(coins, amount);
        System.out.println("count = " + count);
        return res;
    }

    /**
     * 凑硬币问题，递归带备忘录
     *
     * @param coins  硬币面额
     * @param amount 需要凑的总金额
     * @return 凑 amount 需要的最小硬币数量，凑不出来时返回 -1
     */
    public int coinChangeWithDemo(int[] coins, int amount) {

        int[] memo = new int[amount + 1];
        // memo 需要初始化一个取不到的值
        Arrays.fill(memo, -666);

        int res = dp(memo, coins, amount);
        System.out.println("count = " + count);

        return res;
    }

    // 定义：凑 amount 需要的最小硬币数量，凑不出来时返回 -1
    private int dp(int[] coins, int amount) {

        // base case
        if (amount < 0) return -1;
        if (amount == 0) return 0;

        int res = Integer.MAX_VALUE;

        for (int coin : coins) {

            // 分解成多叉树子问题
            int subProblem = dp(coins, amount - coin);
            count++;
            // 子问题无解则跳过
            if (subProblem == -1) continue;
            // 选择最优解
            res = Math.min(res, subProblem + 1);
        }

        return res == Integer.MAX_VALUE ? -1 : res;
    }

    // 定义：凑 amount 需要的最小硬币数量，凑不出来时返回 -1
    private int dp(int[] memo, int[] coins, int amount) {

        // base case
        if (amount < 0) return -1;
        if (amount == 0) return 0;

        int res = Integer.MAX_VALUE;

        for (int coin : coins) {

            int subProblem;
            if (memo[amount] != -666) {
                // 查备忘录
                subProblem = memo[amount];
            } else {
                // 分解成多叉树子问题，记录此步骤执行次数，看一下备忘录的作用
                subProblem = dp(coins, amount - coin);
                count++;
            }

            // 子问题无解则跳过
            if (subProblem == -1) continue;
            // 选择最优解
            res = Math.min(res, subProblem + 1);

            // 存备忘录
            memo[amount] = res;
        }

        return res == Integer.MAX_VALUE ? -1 : res;
    }
}
